Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 10229 - Modular Fibonacci / 10229.cpp
blobdf7e5e26530fcefb206747496654a95c4c38bab3
1 using namespace std;
2 #include <algorithm>
3 #include <iostream>
4 #include <iterator>
5 #include <sstream>
6 #include <fstream>
7 #include <cassert>
8 #include <climits>
9 #include <cstdlib>
10 #include <cstring>
11 #include <string>
12 #include <cstdio>
13 #include <vector>
14 #include <cmath>
15 #include <queue>
16 #include <deque>
17 #include <stack>
18 #include <list>
19 #include <map>
20 #include <set>
22 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
23 #define D(x) cout << #x " is " << x << endl
25 int mod;
26 struct matrix{
27 //2 x 2 matrix:
28 //a b
29 //c d
30 int a, b, c, d;
31 matrix(){}
32 matrix(int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {}
33 const matrix operator * (const matrix &t){
34 long long A = 1LL * a * t.a + 1LL * b * t.c;
35 long long B = 1LL * a * t.b + 1LL * b * t.d;
36 long long C = 1LL * c * t.a + 1LL * d * t.c;
37 long long D = 1LL * c * t.b + 1LL * d * t.d;
38 if (A >= mod) A %= mod;
39 if (B >= mod) B %= mod;
40 if (C >= mod) C %= mod;
41 if (D >= mod) D %= mod;
42 return matrix(A, B, C, D);
46 //returns p^n
47 matrix pow(const matrix &p, int n){
48 if (n == 1) return p;
49 matrix k = pow(p, n/2);
50 matrix ans = k*k;
51 if (n & 1) ans = ans * p;
52 return ans;
55 int main(){
56 int n, m;
57 while (cin >> n >> m){
58 mod = 1 << m;
59 if (n == 0){ cout << 0 << endl; continue; }
60 matrix fib = pow(matrix(0, 1, 1, 1), n);
61 cout << fib.b << endl;
63 return 0;
66 It can be proved by induction that:
68 _ _ ^ n _ _
69 | 0 1 | = | fib(n-1) fib(n) |
70 |_0 1_| |_ fib(n) fib(n+1) _|